package datastructure.trie;

/**
 * 前缀树 + 记忆化搜索
 */
class 键值映射_677 {

    private 键值映射_677[] children = new 键值映射_677[26];
    private int sum = 0;
    private int val = 0;

    public 键值映射_677() {
    }

    public void insert(String key, int val) {
        键值映射_677 node = this;
        for (int i = 0; i < key.length(); i++) {
            int idxInChild = key.charAt(i) - 'a';
            if (node.children[idxInChild] == null) {
                node.children[idxInChild] = new 键值映射_677();
            }
            node = node.children[idxInChild];
            // 修改后重置sum  记忆化失效  下次查询重置
            node.sum = 0;
        }
        node.val = val;
    }

    public int sum(String prefix) {
        键值映射_677 node = this;
        for (int i = 0; i < prefix.length(); i++) {
            int idxInChild = prefix.charAt(i) - 'a';
            if (node.children[idxInChild] == null) {
                return 0;
            }
            node = node.children[idxInChild];
        }
        if (node.sum == 0) {
            dfs(node);
        }
        return node.sum;
    }

    /**
     * 深度优先递归
     * 1. 判断node是否sum过了
     * 2. 如未sum过  加上本身val和所有子val
     */
    private int dfs(键值映射_677 node) {
        if(node == null) return 0;
        if (node.sum != 0) return node.sum;
        int sum = node.val;
        for (键值映射_677 child : node.children) {
            sum += dfs(child);
        }
        node.sum = sum;
        return sum;
    }

}